#include "TopK.h"
void Swap(int* x,int* y)//交换
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}
void AdjustDown(int *arr,int parent,int size)//向下调整，组成大堆
{
    int child = parent*2 + 1;
    while (child < size)
    {
        if(child + 1 < size && arr[child] > arr[child+1])
        {
            child = child + 1;
        }
        if(arr[parent] > arr[child])
        {
            Swap(&arr[parent],&arr[child]);
            parent = child;
            child = parent*2 + 1;
        }
        else
        {
            break;
        }

    }
}
void CreateNDate()
{
    int n = 100;
    FILE *data = fopen("data","w");
    if(data == NULL)
    {
        perror("fopen fail");
        exit(-1);
    }
    srand(time(0));
    for (int i = 0; i < n; ++i)
    {
        int x = rand() % 100;
        fprintf(data,"%d\n",x);
    }
    fclose(data);
}
void PrintTopK(const char* filename,int k)//打印前K个大的数据
{
    //打开文件
    FILE *fout = fopen(filename,"r");
    if(fout == NULL)
    {
        perror("fopen fail");
        exit(-1);
    }
    //开辟k个整型空间
    int* minheap = (int*)malloc(sizeof (int)*k);
    if(minheap == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    //取文件前k个数据放入数组中
    for (int i = 0; i < k; ++i)
    {
        fscanf(fout,"%d",&minheap[i]);
    }
    //对数组元素进行大堆调整
    for(int i = (k-1-1)/2; i >= 0; i--)
    {
        AdjustDown(minheap,i,k);
    }

    for (int i = 0; i < k; ++i)
    {
        printf("%d ",minheap[i]);
    }
    printf("\n");

    //从文件中找数
    int x = 0;
    while(fscanf(fout,"%d",&x) != EOF)
    {
        if(x > minheap[0])
        {
            minheap[0] = x;
            AdjustDown(minheap,0,k);
        }
    }

    for (int i = 0; i < k; ++i)
    {
        printf("%d ",minheap[i]);
    }
    printf("\n");

    fclose(fout);
}